package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 208. 实现 Trie (前缀树)
 * Trie，又称前缀树或字典树，是一棵有根树
 * 使用HashMap来动态分叉
 *
 * @author fy
 * @date 2022/4/18 21:28
 */
public class Solution208 {

    class Trie {

        // 类, 属性, 构造方法都可以private, 外部类可以访问到
        private class Node {
            private boolean isWord;
            private Map<Character, Node> next;

            private Node() {
                this(false);
            }

            private Node(boolean isWord) {
                this.isWord = isWord;
                this.next = new HashMap<>();
            }
        }

        private Node root;

        public Trie() {
            root = new Node();
        }

        public void insert(String word) {
            Node parent = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                if (parent.next.get(ch) == null) {
                    parent.next.put(ch, new Node());
                }
                parent = parent.next.get(ch);
            }
            if (!parent.isWord) {
                parent.isWord = true;
            }
        }

        public boolean search(String word) {
            Node node = searchPrefix(word);
            return node != null && node.isWord;
        }

        public boolean startsWith(String prefix) {
            Node node = searchPrefix(prefix);
            return node != null;
        }

        /**
         * 查找前缀node
         *
         * @param prefix
         * @return
         */
        private Node searchPrefix(String prefix) {
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                char ch = prefix.charAt(i);
                if (cur.next.get(ch) == null) {
                    return null;
                }
                cur = cur.next.get(ch);
            }
            return cur;
        }

    }

}
